The present invention relates to digital watermarking of data including image, video and multimedia data. Specifically, the invention relates to a method for encoding messages into relatively short, non-binary signals. It further relates to a method for decoding the messages from signals while simultaneously distinguishing signals that include encoded messages from signals that are simply noise. It is intended for application in storing information into media watermarks, but it also has application in other areas.
U.S. patent application Ser. No. 08/534,894, filed Sep. 28, 1995, entitled xe2x80x9cSecure Spread Spectrum Watermarking in Multimedia Data, now U.S. Pat. No. 5,930,369xe2x80x9d, and U.S. patent application Ser. No. 08/746,022, filed Nov. 5, 1996, entitled xe2x80x9cDigital Watermarking, now U.S. Pat. No. 5,915,027xe2x80x9d, which are both incorporated herein by reference, describe methods of hiding and detecting relatively short, possibly non-binary vectors, or xe2x80x9cwatermarksxe2x80x9d, in various kinds of media, such as images, audio sequences, and video clips. Such methods are also described in article by Cox et al. entitled xe2x80x9cSecure Spread Spectrum Watermarking for Images, Audio and Videoxe2x80x9d in Proc. IEEE Int. Conf. On Image Proc, ICIP ""96, Lausanne, 1996, vol. III, pp. 243-246. The detection methods described in those inventions and in the Cox et al. article are capable of testing for the presence or absence of only one such hidden vector or watermark at a time. In applications where a given portion of media contains more than one hidden vector, each encoding a different message, the detector must sequentially test for each possible vector and identify the one that is most likely. This is feasible for small numbers of possible messages, but becomes too costly when the number of messages becomes large.
If the data hiding methods referred to above are to be used for messages of more than a small number of bits, such as 4, then methods must be devised for a) encoding bit sequences into vectors suitable for data hiding, b) decoding vectors that are extracted from portions of media, and c) determining whether such extracted vectors represent true hidden data or are merely noise signals. These problems are analogous to those found in transmitting data across noisy channels, where the vectors that are hidden in images are analogous to the modulated signals sent across the channels. Because of this analogy, the terms xe2x80x9cvectorxe2x80x9d and xe2x80x9csignalxe2x80x9d will be used interchangeably.
Standard methods of transmitting binary messages across possibly noisy channels involve two basic steps at the transmitter. First, the message is encoded with an error-correction code. This increases the number of bits in the message, introducing a pattern of redundancy that can be exploited at the receiver to correct errors resulting from noise in the channel. Second, the expanded message is modulated into a signal with physical characteristics suitable for transmission over the channel, by, for example, modulating the amplitude of a carrier signal (AM), modulating the frequency of a carrier signal (FM), or spread-spectrum coding. While standard error-correction codes are directly suitable for the coding of messages for the watermarking methods referred to above, the standard methods of modulation are not so well suited. Since they encode bits sequentially, they have difficulty encoding more than a small number of bits into the relatively short vectors used in electronic watermarks. For example, consider coding 32 bits into a watermark vector of length 64. Each bit would be coded with only two samples, which is not enough to reliably carry information using AM, FM, or spread-spectrum techniques.
An alternative method of converting the error-correction-encoded bits into a vector suitable for a watermark is to treat each bit as a separate channel in a multi-channel communications system. In such a system, each channel is assigned a separate carrier or spread-spectrum signal, and the modulated messages for all the channels are added together into a single signal. At the receiver, separate correlations are performed for each of the channels, and the correlations are compared against a threshold, to obtain each of the transmitted messages in parallel.
The multi-channel approach can be applied to watermarking by assigning a separate xe2x80x9creference signalxe2x80x9d to each bit. These reference signals are designed to have low correlation with one another. The watermark is constructed by either adding or subtracting each reference signal according to whether the corresponding bit is 1 or 0, respectively. Alternatively, the watermark might be constructed by either adding or not adding each reference signal according to whether the corresponding bit is 1 or 0, respectively. Watermarks are decoded by computing their correlations with the reference signals, and comparing the correlations with a pair of thresholds to determine whether the corresponding bits are 1 or 0. Approaches of this type have been applied to watermarking in, for example, the following publications: Swanson, et al., entitled xe2x80x9cRobust Data Hiding for Imagesxe2x80x9d in Proc. IEEE Digital Signal Processing Workshop, Loen, Norway, Sept., 1996; Hartung, et al., entitled xe2x80x9cDigital Watermarking of Raw and Compressed Videoxe2x80x9d in Digital Compression Technologies and Systems for Video Communications, Oct. 1996; and Smith, et al., entitled xe2x80x9cModulation and Information Hiding in Imagesxe2x80x9d in Proc. Int. Workshop on Information Hiding, May 1996.
A principal problem with these approaches is that they are limited to only one type of detection region for the possible watermarks. In the prior art, the region of watermark space that is decoded to a given bit sequence results in detection regions that are all planes, intersecting at right angles. Such a rectangular detection region is appropriate for many data transmission systems, but for some systems, other shapes of detection regions are desirable. This is particularly true of watermarking.
The present invention solves the problem of hiding messages of 8 or more bits into media. The invention provides a method of encoding a message, described as a sequence of a given number, B, of bits, into a vector suitable for hiding in media by means of the data hiding methods referred to above. This encoding method is a procedure by which one of 2B possible vectors is generated. The invention further provides a method of decoding a given, possibly distorted, vector into the sequence of B bits that is most likely encoded by the bit sequence. Finally, the invention also provides a method for quickly deciding whether a given vector is one of the 2B vectors that can be generated by the encoding process, or whether the vector is simply a noise signal. This last feature of the invention is important in deciding whether or not a given piece of media contains hidden information at all.
The detection regions (described below) employed in the detection of hidden data can be fairly arbitrary when practicing the present invention.
While the present invention solves the problem of hiding messages in media, it has application in other areas as well. In particular, the invention is suitable for use in any application where rectilinear detection regions are sub-optimal.
A primary object of the invention is a decoder which, after decoding a vector into a bit sequence, re-encodes that bit sequence and compares the resulting vector with the original vector to determine whether the original vector truly encoded a message or was simply a noise signal. A principal advantage of this approach is that it allows any type of comparison test to be performed, resulting in any shape of detection region. By proper design of the comparison test, an optimal detection region can be created.
A second object of the invention is a method of adding and using a synchronization signal to the encoded vector without disturbing the detectability of the encoded message. The synchronization signal is used to compensate for the possibility that the received vector is cyclically rotated from the original. The method splits the vector into two halves. During encoding, the encoder first determines an encoding of the message into a vector half the length of the eventual encoded vector. This half-length vector forms the first half of the encoded vector, and is negated to form the second half of the encoded vector. Then the encoder adds an identical synchronization signal to both halves of the encoded vector. During decoding, the decoder first obtains the synchronization signal by adding the two halves of the vector together, canceling the encoded message. The synchronization signal is used to find the original cyclical shift of the vector. Then the decoder obtains the half-length encoded message vector by taking the difference between the two halves of the aligned, full-length encoded vector.
Further objects of the invention will become more clearly apparent when the following description is read in conjunction with the accompanying drawing.